class Solution
{
public:
    int squareFreeSubsets(vector<int> &nums)
    {
        unordered_set<int> squareFreeNums{2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30};
        auto factorMask = [](int n)
        {
            int i = 2;
            int mask = 0;
            while (i <= n)
            {
                if (n % i == 0)
                {
                    mask |= 1 << i;
                    n /= i;
                }
                else
                {
                    ++i;
                }
            }
            return mask;
        };

        unordered_map<int, int> prevMaskCount;
        prevMaskCount[0] = 1;

        long long result = 0;
        int oneCount = 0;
        for (int num : nums)
        {
            if (num == 1)
            {
                ++oneCount;
            }
            else if (squareFreeNums.count(num))
            {
                unordered_map<int, int> incMaskCount;
                for (auto &[prevMask, count] : prevMaskCount)
                {
                    int numMask = factorMask(num);
                    if ((numMask & prevMask) == 0)
                    {
                        result += count;
                        result %= 1'0000'0000'7;
                        incMaskCount[numMask | prevMask] += count;
                    }
                }
                for (auto &[mask, count] : incMaskCount)
                {
                    prevMaskCount[mask] += count;
                    prevMaskCount[mask] %= 1'0000'0000'7;
                }
            }
        }
        long long oneCasesCount = 1;
        for (int i = 1; i <= oneCount; ++i)
        {
            oneCasesCount *= 2;
            oneCasesCount %= 1'0000'0000'7;
        }
        result = (result * oneCasesCount + oneCasesCount - 1) % 1'0000'0000'7;
        return result;
    }
};